"""
https://leetcode.cn/problems/maximal-square/description/

221. 最大正方形
已解答
中等
相关标签
相关企业
在一个由 '0' 和 '1' 组成的二维矩阵内，找到只包含 '1' 的最大正方形，并返回其面积。

 

示例 1：


输入：matrix = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]]
输出：4
示例 2：


输入：matrix = [["0","1"],["1","0"]]
输出：1
示例 3：

输入：matrix = [["0"]]
输出：0
 

提示：

m == matrix.length
n == matrix[i].length
1 <= m, n <= 300
matrix[i][j] 为 '0' 或 '1'

"""
from typing import List


class Solution:
    """
    最朴素的思路，是遍历每一个单元格，遍历其最大边长。
    但这样时间复杂太高。
    实际采用动态规划来做。
    dp(i,j)表示从(0,0)到(i,j)的矩阵中，以i,j为右下角的最大正方形的边长。
    如果dp(i,j)=n，等同于满足：
    1. (i-n,j-n)到(i,j)的所有单元格均为1；翻译：对于任意的x,y，如果i-n<=x<=i且j-n<=y<=j,则val(x,y)=1
    2. 对于(i-n-1,x)和(j-n-1,y),其中x>=j-n-1以及y>=x-n-1的所有元素中，至少有一个元素为0或不存在。

    先给出结论：if val(i+1,j+1)=1,then dp(i+1,j+1)=min(dp(i,j),dp(i,j+1),dp(i+1,j))+1;else dp(i+1,j+1)=0
    证明如下：
    假定m=min(dp(i,j),dp(i,j+1),dp(i+1,j))
    根据dp(i,j)的定义，由于m<=dp(i,j)，可以得知：
    对于任意的x,y，如果i-m<=x<=i且j-m<=x<=j，则val(x,y)=1
    同理，
    对于任意x,y，如果i+1-m<=x<=i+1且j-m<=y<=j，则val(x,y)=1
    对于任意x,y，如果i-m<=x<=i且y-m+1<=y<=j+1，则val(x,y)=1
    所以，if val(i+1,j+1)=1,then 对于任意的i-m<=x<=i+1且j-m<=y<=j+1 (这中间涉及条件的合并，可以从图形上理解，也可以按照相同部分条件合并的方式理解)
    
    条件1得以证明；
    条件2可用反证法，容易说明，此处不再赘述
    

    """
    def maximalSquare(self, matrix: List[List[str]]) -> int:
        h=len(matrix)
        w=len(matrix[0])
        dp=[[0 for _ in range(w)]for _ in range(h)]

        max_len=0
        for row in range(h):
            for col in range(w):
                if row==0 or col==0:
                    dp[row][col]=1 if matrix[row][col]=='1' else 0
                    max_len=max(max_len,dp[row][col])
                elif matrix[row][col]=='1':
                    dp[row][col]=min(dp[row-1][col-1],dp[row-1][col],dp[row][col-1])+1
                    max_len=max(max_len,dp[row][col])
        
        return max_len**2

if __name__=='__main__':
    matrix = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]]
    s=Solution()
    res=s.maximalSquare(matrix)
    print(res)